class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        node1 = l1
        n1 = 0
        while node1:
            n1 += 1
            node1 = node1.next
        node2 = l2
        n2 = 0
        while node2:
            n2 += 1
            node2 = node2.next

        def search(node1, node2, k1, k2):
            if k1 == 1 and k2 == 1:
                a = (node1.val + node2.val) // 10
                node1.val = (node1.val + node2.val) % 10
                return node1, a
            if k1 == k2:
                next_node, next_a = search(node1.next, node2.next, k1 - 1, k2 - 1)
                now_sum = node1.val + node2.val + next_a
                now_a = now_sum // 10
                node1.val = now_sum % 10
                node1.next = next_node
                return node1, now_a
            if k1 > k2:
                next_node, next_a = search(node1.next, node2, k1 - 1, k2)
                now_sum = node1.val + next_a
                now_a = now_sum // 10
                node1.val = now_sum % 10
                node1.next = next_node
                return node1, now_a
            if k1 < k2:
                next_node, next_a = search(node1, node2.next, k1, k2 - 1)
                now_sum = node2.val + next_a
                now_a = now_sum // 10
                node2.val = now_sum % 10
                node2.next = next_node
                return node2, now_a

        head, next_a = search(l1, l2, n1, n2)
        if next_a:
            head = ListNode(1, head)
        return head
